1. Field of the Invention
The present invention relates to a route planning method and a route planning device for planning a travel route, and an autonomous mobile device.
2. Description of the Related Art
A conventional autonomous mobile device autonomously travels from the starting point (starting position) to the destination (goal position) along a planned route while avoiding contact with obstacles. As this kind of autonomous mobile device, a mobile robot (autonomous mobile device) which autonomously controls the travel speed and travel direction according to ambient environmental conditions (ambient brightness and the like, for example) is disclosed in Japanese Patent Application Laid-open No. 2007-213111. This mobile robot travels at a fast speed if the ambient environmental conditions are favorable, and drops its travel speed if the ambient environmental conditions are inferior in order to avoid contact with obstacles.
Meanwhile, when planning an autonomous travel route, for example, SLAM (Simultaneous Localization and Mapping) technology or the like is used to generate an environmental map (map showing an area containing obstacles and an area that does not contain obstacles) in which an xy plane is subject to grid division, a movable area is extracted from the environmental map, and the starting position and goal position instructed by the user are connected along the movable area in order to plan the travel route.
Upon extracting a movable area from the environmental map, a method of extending (expanding) the boundary of the obstacle area in an amount corresponding to the size of the autonomous mobile device so that the size of the autonomous mobile device can be viewed as a point, is used. As this kind of method of extending the boundary of the obstacle area, a method using a potential function is described in Japanese Patent Application Laid-open No. H7-129238. According to the method described in Japanese Patent Application Laid-open No. H7-129238, foremost, a potential function having a certain potential value in the obstacle area and which monotonically decreases according to the distance from the obstacle area is considered, and a potential field in which the sum of the value calculated with the potential function relative to the respective grids of the movable area as the potential value of that location is created. Subsequently, by using this potential field, an area in which the potential value becomes a predetermined threshold or more is added as a new obstacle area to the original obstacle area.
Moreover, an area in which the potential value becomes less than a predetermined threshold is deemed a new movable area.
More specifically, with this route generation method, the travel route is generated according to the following routine.
1. A topographic map is generated with topographic data obtained as a result of the distance measurement using a laser range finder.
2. A potential field is generated so that an obstacle area becomes a ridge and a travelable area becomes a valley relative to the generated topographic map. An area in which the potential value becomes a predetermined value or greater, is redefined as an obstacle area. An area in which the potential value becomes less than a predetermined value is redefined as a travelable area.
3. The overall travelable area is divided into partial areas that are represented as an aggregate of intervals of other directions which are different from the reference direction that corresponds one-on-one to the respective coordinates of the reference direction as a result of dividing the travelable area at the branching or connecting points of the travelable area relative to the reference direction, and expressing the result as a graph structure with the partial areas as the node and the connection relation between the partial area as the arc.
4. The route length of the polygonal route connecting the starting point, the pass points selected theretofore, and the goal point is considered as the distance predictive value. The halfway passage area sequence and the pass point sequence of the route from the starting point to the goal point are searched and decided based on the graph structure so as to minimize the route length.
5. The collision check of the polygonal route connecting the pass points and the obstacle area is performed using the interval information of the nodes of the graph structure, and a polygonal route that will not collide with the obstacle area is generated by adding, to the polygonal apex sequence, the boundary point sequence corresponding to the portion that will collide with the obstacle area on the polygonal route or the point sequence with an appropriate offset provided thereto.
Here, the control cycle and the control delay cannot be set to zero upon performing the travel control of the autonomous mobile device. Thus, the actual behavior of an autonomous mobile device is subject to a slight error (response lag) relative to the intended behavior. Note that this error becomes more prominent as the travel speed increases. Meanwhile, the clearance (width of passage) of the route on which the autonomous mobile device travels is not always constant. Thus, with the mobile robot described in Japanese Patent Application Laid-open No. 2007-213111, in cases where the autonomous mobile device passes through, for example, a narrow passage (route) or avoids an obstacle in a narrow passage, there was a possibility that it would come in contact with the obstacle due to the influence of the foregoing error. Accordingly, under circumstances where it is only known that the autonomous mobile device can pass through the pass-through point on the route, it was necessary to travel at a slow speed in order to reduce the foregoing error regardless of whether the passage (route) was sufficiently wide or narrow.
According to the foregoing route generation method, the route is planned by determining that it can be passed through if the potential value is less than a predetermined threshold, but no consideration is given to comprehending, in advance, the clearance (width of passage) of the planned route. Specifically, although the route clearance at the pass-through points on the travel route is often different for each pass-through point, with the foregoing route generation method, it was not possible to comprehend, in advance, the route clearance of each pass-through point on the planned travel route. Thus, in consideration of the control cycle and control delay, it was necessary to travel at a slow speed even at locations where the route has clearance in the same manner upon traveling on a route with no clearance.
Moreover, according to the foregoing route generation method, it is possible to generate a polygonal route that does not collide with the obstacle area. Nevertheless, with this method, since a polygonal route that will not collide with the obstacle area is generated by adding, to the polygonal apex sequence, the boundary point sequence corresponding to the portion that will collide with the obstacle area on the polygonal route or the point sequence with an appropriate offset provided thereto, depending on the shape of the obstacle area, there is a possibility that a polygonal route of a complex shape (for example a zigzag route, a route with sharp bends, and so on) may be generated. Thus, there was a possibility that the generated travel route would not necessarily be a shape that is suitable for the travel of the autonomous mobile device from the perspective of the motion performance (motion characteristics) of the autonomous mobile device. Specifically, cases where the autonomous mobile device could not actually travel along the generated polygonal route, or would vibrate upon traveling along the generated polygonal route may have occurred.